#include <stdio.h>
#include <stdlib.h>

struct NODE
{
    int value;
    struct NODE *next;
    struct NODE *prev;
};

//创建一个新节点
struct NODE *createNode(int value)
{
    struct NODE *newNode = (struct NODE *)malloc(sizeof(struct NODE));
    
    if(newNode == NULL)
    {
        perror("内存创建失败！");
        return NULL;
    }

    newNode->value = value;
    newNode->prev = NULL;
    newNode->next = NULL;

    return newNode;
}

//头插法
struct NODE *insertHead(struct NODE* head,int value)
{
    struct NODE *newNode = createNode(value);
    if(!newNode) return head;

    if(head == NULL) return newNode;

    newNode->next = head;
    head->prev = newNode;

    return newNode;
}

//尾插法
struct NODE *insertTail(struct NODE* head,int value)
{
    struct NODE *newNode = createNode(value);
    
    if(head == NULL)
        return newNode;
    
    struct NODE* p = head;
    while(p->next != NULL)
    {
        p = p->next;
    }

    p->next = newNode;
    newNode->prev = p;

    return head;
}

//计算链表长度
int countList(struct NODE* head)
{
    int count = 0;
    while(head != NULL)
    {
        head = head->next;
        count++;
    }
    return count;
}

//任意位置插入,从0开始
struct NODE* insert(struct NODE *head,int pos,int value)
{
    int count = countList(head);
    if(pos < 0 || pos > count) return head;

    if(pos == count)
        return insertTail(head,value);
    
    if(pos == 0)
        return insertHead(head,value); 

    struct NODE *newNode = createNode(value);
    if(!newNode) return head;

    struct NODE* p = head;
    for(int i = 0; i < pos-1;i++)
    {
        p = p->next;
    }

    newNode->next = p->next;
    p->next->prev = newNode;
    p->next = newNode;
    newNode->prev = p;
    
    return head; 
}

//删除链表的任意一个位置
struct NODE* removeNode(struct NODE * head,int pos)
{
    if(head == NULL)
        return NULL;

    int count = countList(head); 
    if(pos < 0 || pos >= count)
        return head; 
    
    struct NODE* p = head;
    if(pos == 0)
    {
        head = head->next;
        if(head != NULL)
            head->prev = NULL;
        
        free(p);
        return head; 
    }
    for(int i = 0; i < pos; i++)
    {
        p = p->next;
    }

    if(p->prev != NULL)
        p->prev->next = p->next;

    if(p->next != NULL)
        p->next->prev = p->prev;

    free(p);

    return head;
}

//销毁链表
void distoryList(struct NODE* head)
{
    struct NODE* p = head;


    while(head != NULL)
    {
        head = head->next;
        free(p);
        p = head;
    }
}

//显示链表
void displayList(struct NODE *head)
{
    while(head != NULL)
    {
        printf("%d ",head->value);
        head = head->next;
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    struct NODE* head = NULL;

    //头插法
    // head = insertHead(head,5);
    // head = insertHead(head,4);
    // head = insertHead(head,3);
    // head = insertHead(head,2);
    // head = insertHead(head,1);

    //尾插法
    head = insertTail(head,1);
    head = insertTail(head,2);
    head = insertTail(head,3);
    head = insertTail(head,4);
    head = insertTail(head,5);

    //任意位置插入
    // head = insert(head,10,0);

    head = removeNode(head,0);

    //显示链表
    displayList(head);

    distoryList(head);

    return 0;
}
